package puzzle.projecteuler.p200;


public class Problem164 {

	/**
	 * f(n, i, j) 表示满足条件的,末两位是ij的n位数的个数
	 * 
	 * answer	: 378158756814587
	 * time cost: 16 ms
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		
		//init
		int n = 3;
		long[][] f = new long[10][];
		for (int i = 0; i < f.length; i ++) {
			f[i] = new long[10];
			for (int j = 0; j < f[i].length; j ++) {
				f[i][j] = (i + j <= 9)?(9-i-j):0; 
			}
		}
		//iteration
		while (n < 20) {
			n ++;
			long[][] g = new long[10][];
			for (int i = 0; i < g.length; i ++) {
				g[i] = new long[10];
				for (int j = 0; j < g[i].length; j ++) {
					g[i][j] = f[i][j]; 
				}
			}
			
			for (int i = 0; i < f.length; i ++) {
				for (int j = 0; j < f[i].length; j ++) {
					f[i][j] = 0;
					for (int k = 0; k <= (9-i-j); k ++) {
						f[i][j] += g[k][i];
					}
				}
			}
		}
		//result
		long sum = 0;
		for (int i = 0; i < f.length; i ++) {
			for (int j = 0; j < f[i].length; j ++) {
				sum += f[i][j];
			}
		}
		System.out.println(sum);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
}
